package com.demo.java.OD251_300.OD255;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【查找树中的元素 or 查找二叉树节点】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146054470
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取节点数
        int n = Integer.parseInt(scanner.nextLine());

        // 存储每个节点的信息
        List<Integer[]> nodesInfo = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nodesInfo.add(Arrays.stream(scanner.nextLine().split(" ")).map(
                    Integer::parseInt).toArray(Integer[]::new));
        }

        // 获取查询的节点x和查询位置y
        int x = scanner.nextInt(), y = scanner.nextInt();

        // 输出查询结果
        System.out.print(getResult(nodesInfo, x, y));
    }

    // 获取查询结果的方法
    private static String getResult(List<Integer[]> nodes, int x, int y) {
        if (x < 0 || y < 0) return "{}";  // 如果x或y为负，返回空集合

        Map<String, List<Integer>> memo = new HashMap<>();
        List<Integer> list = calc(nodes, 0, x, memo);

        // 如果查询位置y大于list大小，则返回空集合
        if (y >= list.size()) return "{}";

        return "{" + list.get(y) + "}";  // 返回查询的节点的值
    }

    // 递归计算节点的值
    private static List<Integer> calc(List<Integer[]> nodes, int index, int n,
                                      Map<String, List<Integer>> memo) {
        String key = index + "," + n;  // 生成缓存的key
        return memo.computeIfAbsent(key, k -> {
            Integer[] node = nodes.get(index);  // 获取当前节点
            List<Integer> list = new ArrayList<>();
            if (n == 0) {
                list.add(node[0]);  // 如果n为0，则添加当前节点的值
            } else if (node.length > 1) {
                list.addAll(Arrays.stream(node, 1, node.length)  // 递归查询子节点
                        .flatMap(i -> calc(nodes, i, n - 1, memo).stream())
                        .collect(Collectors.toList()));
            }
            return list;
        });
    }
}